package com.lw.leetcode.dp.b;

/**
 * 1043. 分隔数组以得到最大和
 *
 * @Author liw
 * @Date 2021/5/29 18:28
 * @Version 1.0
 */
public class MaxSumAfterPartitioning {

    public static void main(String[] args) {
        MaxSumAfterPartitioning test = new MaxSumAfterPartitioning();
        int[] arr = {1,15,7,9,2,5,10};
        int i = test.maxSumAfterPartitioning(arr, 3);
        System.out.println(i);
    }

    public int maxSumAfterPartitioning(int[] arr, int k) {
        int length = arr.length;
        int[] dp = new int[length + 1];

        for (int i = 1; i <= length; i++) {
            int max = arr[i - 1];
            int st = i - k + 1  <= 1 ? 1 : i - k + 1;
            for (int j = i; j >= st; j--) {
                max = Math.max(max, arr[j - 1]);
                dp[i] = Math.max(dp[j - 1] + max * (i - j + 1), dp[i]);
            }
        }
        return dp[length];
    }
}
